package com.cg.leetcode;

import org.junit.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 542.01矩阵
 *
 * @program: LeetCode->LeetCode_542
 * @description: 542.01矩阵
 * @author: cg
 * @create: 2021-09-24 19:02
 **/
public class LeetCode_542 {

    @Test
    public void test542() {
        //System.out.println(Arrays.deepToString(updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}})));
        //System.out.println(Arrays.deepToString(updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}})));
        //System.out.println(Arrays.deepToString(updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 0}})));
        System.out.println(Arrays.deepToString(updateMatrix(new int[][]{{0, 0, 0, 1}, {0, 1, 1, 0}, {1, 1, 1, 1}, {0, 1, 0, 0}})));
    }

    /**
     * 给定一个由 `0` 和 `1` 组成的矩阵 `mat` ，请输出一个大小相同的矩阵，其中每一个格子是 `mat` 中对应位置元素到最近的 `0` 的距离。
     * 两个相邻元素间的距离为 `1` 。
     * <p>
     * 示例 1：
     * 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：[[0,0,0],[0,1,0],[0,0,0]]
     * <p>
     * 示例 2：
     * 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
     * 输出：[[0,0,0],[0,1,0],[1,2,1]]
     * <p>
     * 提示：
     * 1) m == mat.length
     * 2) n == mat[i].length
     * 3) 1 <= m, n <= 10的4次幂
     * 4) 1 <= m * n <= 10的4次幂
     * 5) mat[i][j] is either 0 or 1.
     * 6) mat` 中至少有一个 `0
     *
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] seen = new boolean[m][n];
        Deque<int[]> queue = new LinkedList<>();
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true;
                }
            }
        }

        // 广度优先搜索
        while (!queue.isEmpty()) {
            int[] cell = queue.remove();
            int x = cell[0], y = cell[1];
            for (int d = 0; d < 4; ++d) {
                int ni = x + DIRS[d][0];
                int nj = y + DIRS[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[x][y] + 1;
                    queue.offer(new int[]{ni, nj});
                    seen[ni][nj] = true;
                }
            }
        }
        return dist;
    }
    final static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


}
